#include "calculate.h"
#include "tree.h"

// 最大公因数
static u32_s _gcd(u32_s num1, u32_s num2) {
	u32_s max;
	u32_s min;
	if (num1 <= num2) {
		max = num2;
		min = num1;
	} else {
		max = num1;
		min = num2;
	}
	while (min != 0) {
		u32_s new_min = max % min;
		max = min;
		min = new_min;
	}
	return max;
}

// 约分
static fraction_t _reduce(i32_s numerator, u32_s denominator) {
	u32_s abs_numerator;
	if (numerator >= 0) {
		abs_numerator = numerator;
	} else {
		abs_numerator = -numerator;
	}
	u32_s gcd = _gcd(abs_numerator, denominator);
	fraction_t result;
	// gcd ==
	// 0仅在传入两个参数均为0时才会发生，必然有错误，因此返回0/0即可。
	if (gcd == 0) {
		result.numerator = 0;
		result.denominator = 0;
	} else {
		result.numerator = numerator / gcd;
		result.denominator = denominator / gcd;
	}
	return result;
}

// 加法
static fraction_t _add(fraction_t frac1, fraction_t frac2) {
	u32_s denominator1 = frac1.denominator;
	u32_s denominator2 = frac2.denominator;
	u32_s mul_denominator = denominator1 * denominator2;

	i32_s numerator1 = frac1.numerator;
	i32_s numerator2 = frac2.numerator;
	i32_s result_numerator = numerator1 * (i32_s)denominator2 +
				 numerator2 * (i32_s)denominator1;
	fraction_t result = _reduce(result_numerator, mul_denominator);
	return result;
}

// 减法
static fraction_t _sub(fraction_t frac1, fraction_t frac2) {
	u32_s denominator1 = frac1.denominator;
	u32_s denominator2 = frac2.denominator;
	u32_s mul_denominator = denominator1 * denominator2;

	i32_s numerator1 = frac1.numerator;
	i32_s numerator2 = frac2.numerator;
	i32_s result_numerator = numerator1 * (i32_s)denominator2 -
				 numerator2 * (i32_s)denominator1;
	fraction_t result = _reduce(result_numerator, mul_denominator);
	return result;
}

// 乘法
static fraction_t _mul(fraction_t frac1, fraction_t frac2) {
	i32_s numerator1 = frac1.numerator;
	i32_s numerator2 = frac2.numerator;
	i32_s mul_numerator = numerator1 * numerator2;

	u32_s denominator1 = frac1.denominator;
	u32_s denominator2 = frac2.denominator;
	u32_s mul_denominator = denominator1 * denominator2;

	fraction_t result = _reduce(mul_numerator, mul_denominator);
	return result;
}

// 除法
static fraction_t _div(fraction_t frac1, fraction_t frac2) {
	i32_s numerator1 = frac1.numerator;
	i32_s numerator2 = frac2.numerator;
	u32_s denominator1 = frac1.denominator;
	u32_s denominator2 = frac2.denominator;
	if (numerator2 == 0) {
		fraction_t invalid = {
			.numerator = 0,
			.denominator = 0,
		};
		return invalid;
	}

	if (numerator2 < 0) {
		numerator1 = -numerator1;
		numerator2 = -numerator2;
	}
	i32_s result_numerator = numerator1 * (i32_s)denominator2;
	u32_s result_denominator = denominator1 * (u32_s)numerator2;

	fraction_t result = _reduce(result_numerator, result_denominator);
	return result;
}

static fraction_t _calculate_sub_tree(const tree34_t* tree_p,
				      const node_t* node_p) {
	// 如果根结点是数字，直接返回简单分数。
	if (!node_is_oper(tree_p, node_p)) {
		i32_s number = node_get_num(tree_p, node_p);
		fraction_t result = {
			.numerator = number,
			.denominator = 1,
		};
		return result;
	}

	// 如果根结点是运算符，进行运算。
	sub_nodes_t sub = node_get_sub(tree_p, node_p);
	fraction_t left_result = _calculate_sub_tree(tree_p, sub.left_p);
	if (left_result.denominator == 0) {
		return left_result;
	}
	fraction_t right_result = _calculate_sub_tree(tree_p, sub.right_p);
	if (right_result.denominator == 0) {
		return right_result;
	}
	oper_e oper = node_get_oper(tree_p, node_p);
	switch (oper) {
	case OPER_ADD:
		return _add(left_result, right_result);

	case OPER_SUB:
		return _sub(left_result, right_result);

	case OPER_MUL:
		return _mul(left_result, right_result);

	case OPER_DIV:
		return _div(left_result, right_result);
	default: {
		fraction_t invalid = {
			.numerator = 0,
			.denominator = 0,
		};
		return invalid;
	}
	}
}

// 对外提供：calculate_tree()
fraction_t calculate_tree(const tree34_t* tree_p) {
	const node_t* node_p = tree_get_head(tree_p);
	return _calculate_sub_tree(tree_p, node_p);
}